package com.markus.code.动态规划;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/15 14:11
 * todo: 最长公共子串的相关问题
 */
public class LCSubstring {
    /**
     *  求出最长公共子串的长度(连续)
     *  这个解法就比较解决了
     *      1、以str1[i]、str2[j]结尾的元素，如果它俩相等
     *          dp[i][j] = dp[i-1][j-1] + 1
     *      2、以str1[i]、str2[j]结尾的元素，如果不相等
     *          dp[i][j] = 0
     */
    public int lcsLength(String str1,String str2){
        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0){
            return 0;
        }
        int dp[][] = new int[str1.length()][str2.length()];
        for (int i=0;i<str2.length();i++){
            dp[0][i] = str1.charAt(0) == str2.charAt(i)?1:0;
        }
        for (int i=0;i<str1.length();i++){
            dp[i][0] = str1.charAt(i) == str2.charAt(0)?1:0;
        }
        for (int i=1;i<str1.length();i++){
            for (int j=1;j<str2.length();j++){
                dp[i][j] = str1.charAt(i)==str2.charAt(j)?dp[i-1][j-1]+1:0;
            }
        }
        int max = 0;
        int end = 0;
        for (int i=0;i<dp.length;i++){
            for (int j=0;j<dp.length;j++){
                if (max < dp[i][j]){
                    end = i;
                    max = dp[i][j];
                }
            }
        }
        return max;
    }
    public String lcs(String str1,String str2){
        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0){
            return "";
        }
        int dp[][] = new int[str1.length()][str2.length()];
        for (int i=0;i<str2.length();i++){
            dp[0][i] = str1.charAt(0) == str2.charAt(i)?1:0;
        }
        for (int i=0;i<str1.length();i++){
            dp[i][0] = str1.charAt(i) == str2.charAt(0)?1:0;
        }
        for (int i=1;i<str1.length();i++){
            for (int j=1;j<str2.length();j++){
                dp[i][j] = str1.charAt(i)==str2.charAt(j)?dp[i-1][j-1]+1:0;
            }
        }
        int max = 0;
        int end = 0;
        for (int i=0;i<dp.length;i++){
            for (int j=0;j<dp.length;j++){
                if (max < dp[i][j]){
                    end = i;
                    max = dp[i][j];
                }
            }
        }
        return str1.substring(end-max+1,end+1);
    }

    /**
     * 压缩空间：用有限几个变量就可以完成这个算法
     */
    public String lcsPushSpace(String str1,String str2){
        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0){
            return "";
        }
        char []strs1 = str1.toCharArray();
        char []strs2 = str2.toCharArray();
        int row = 0;
        int col = strs2.length-1;
        int end = 0;
        int max = 0;
        while(row < strs1.length){
            int i = row;
            int j = col;
            int len = 0;
            while(i<strs1.length && j < strs2.length){
                if (strs1[i] == strs2[j]){
                    len++;
                }else {
                    len = 0;
                }
                if (max < len){
                    end = i;
                    max = len;
                }
                i++;
                j++;
            }
            if (col == 0){
                row++;
            }else{
                col--;
            }
        }
        return str1.substring(end-max+1,end+1);
    }

    public static void main(String[] args) {
        String str1 = "ab2bca3d";
        String str2 = "56abb8a89";
        LCSubstring demo = new LCSubstring();
        System.out.println(demo.lcsLength(str1,str2));
        System.out.println(demo.lcs(str1,str2));
        System.out.println(demo.lcsPushSpace(str1,str2));
    }
}
